package com.tree;

import java.util.Arrays;

/**
 * @BelongsProject: DataStructures
 * @BelongsPackage: com.tree
 * @Author: 江岸
 * @CreateTime: 2021-03-22 20:43
 * @Description: 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] ints = {12, 23, 54, 4, -32, 1, 387};
        new HeapSort().heapSort(ints);
        System.out.println(Arrays.toString(ints));
    }

    public void heapSort(int[] arr){
        int temp=0;
        //(1)将无序序列构成一个堆，根据升序降序需求选择最大顶堆或者最小顶堆。此为大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从最后一个非叶子节点开始进行调整
            adjustHeap(arr,i,arr.length);
        }
        //(2)将堆顶元素与末尾元素交换，将最大元素沉到数组末端
        //(3)重新调整结构（n-1）个元素，反复执行
        for (int j=arr.length-1;j>0;j--){
            //交换
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }
    }


    //将一个数组（二叉树），调整成大顶堆
    /**
     *功能：完成将以i对应的非叶子节点的树调整成大顶堆
     * @param arr 待调整的数组
     * @param i 表示非叶子节点在数组中的索引
     * @param length 表示对多少个元素继续调整
     */
    public void adjustHeap(int[] arr,int i,int length){
        int temp = arr[i];//先取出当前元素的值，保存在临时变量
        //1. k=i*2+1 k是i的左子节点
        for (int k=2*i+1;k<length;k=2*k+1){
            if (k+1<length && arr[k]<arr[k+1]){//说明左子节点的值小于右子节点的值
                k++;//k指向右子节点
            }
            if (temp<arr[k]){//如果子节点大于父节点
                arr[i] = arr[k];//把较大的值赋给当前节点
                i=k;//i指向k，继续循环比较
            }else {
                break;
            }
        }
        //当for循环结束后，我们已经将以i为父节点的树的最大值，放在了最顶(局部)
        arr[i] = temp;//将temp值放到调整后的位置
    }
}
